#include<iostream>
#include<vector>
using namespace std;
/*
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
解题思路：
假如有一个数组{7，1，5，3，6，4}，我们使用一个二维dp数组才能表示每一天（下标）股票的一个状态
每一天股票的状态有两种：持有股票和不持有股票，这两种状态就能包含了买股票和卖出股票，使用dp[i][0]表示持有股票的手上最大本金
dp[i][1]表示不持有股票的手上最大本金
然后分别求出递推公式，持有股票的手上的最大本金dp[i][0]可以有两种状态推出，在第i天之前就已经持有股票了dp[i][0] = dp[i-1][0]
在第i天购入的股票，dp[i][0] = -price[i]这里要用符号表示购入股票手上的本金减少
并且dp[i][0]表示最大值所以dp[i][0] = max(dp[i-1][0],-price[i]);
同理第i天不持有股票也可以是第i天之前就已经卖出了股票dp[i][1] = dp[i-1][1],也可以是在第i天卖出的股票
若是第i天卖出了这股票，那么前一天一定是持有该股票的状态，所以dp[i][1] = dp[i-1][0]+price[i]
所以dp[i][1] = max(dp[i-1][1],dp[i-1][0]+price[i])
然后遍历顺序因为当前的状态都依赖与前一天的状态，所以遍历顺序应该是从前往后遍历
*/
int dp(vector<int> prices)
{
    //创建dp数组并进行初始化
    vector<vector<int>> dp(prices.size(),vector<int>(2));
    //第0天持有该股票的最大本金为-price[0]
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    for(int i=1;i<prices.size();i++)
    {
        dp[i][0] = max(dp[i-1][0],-prices[i]);
        dp[i][1] = max(dp[i-1][0]+prices[i],dp[i-1][1]);
    }
    return dp[prices.size()-1][1];
}
int main()
{
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter nums:"<<endl;
    vector<int> nums(number);
    for(int i=0;i<number;i++)
        cin>>nums[i];
    cout<<dp(nums);
    return 0;
}